1155F - Delivery Oligopoly - CodeForces Solution

#include <bits/stdc++.h>
#define lowbit(x) (x & -x)
#define eb emplace_back
#define pb push_back
#define mp make_pair
using namespace std;

typedef long long ll;
const int N = 15;
const int Mod = 998244353;

int n, m;
int f[1 << 14];
int pg[N][N][1 << 14];
bool g[N][N][1 << 14], G[N][N], cir[1 << 14];
tuple<int, int, int> pf[1 << 14];

inline void print(int S, int i, int j) {
    while (S != (1 << i - 1)) {
        // printf("|%d %d %d|\n", S, i, j);
        printf("%d %d\n", j, pg[i][j][S]);
        int tmp = j;
        j = pg[i][j][S];
        if (tmp != i) S -= (1 << tmp - 1);
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u][v] = G[v][u] = 1;
        g[u][v][(1 << u - 1) | (1 << v - 1)] = 1;
        g[v][u][(1 << u - 1) | (1 << v - 1)] = 1;
        pg[u][v][(1 << u - 1) | (1 << v - 1)] = u;
        pg[v][u][(1 << u - 1) | (1 << v - 1)] = v;
    }

    for (int S = 2; S < 1 << n; S++)
        for (int i = 1; i <= n; i++) if (S >> i - 1 & 1)
            for (int j = 1; j <= n; j++) if (j != i && (S >> j - 1 & 1) && g[i][j][S]) {
                if (G[j][i] && __builtin_popcount(S) > 2) {
                    g[i][i][S] = 1;
                    pg[i][i][S] = j;
                }
                for (int k = 1; k <= n; k++) if (!(S >> k - 1 & 1) && G[j][k]) {
                    g[i][k][S | (1 << k - 1)] = 1;
                    pg[i][k][S | (1 << k - 1)] = j;
                }
            }

    memset(f, 0x3f, sizeof(f));
    f[1] = 0;
    for (int S = 1; S < 1 << n; S++)
        for (int i = 1; i <= n; i++) if (S >> i - 1 & 1)
            for (int j = 1; j <= n; j++) if (S >> j - 1 & 1) {
                int U = (1 << n) - 1 ^ S;
                for (int T = U; T; T = (T - 1) & U)
                    if (g[i][j][T | (1 << i - 1) | (1 << j - 1)] && f[S | T] > f[S] + 1) {
                        f[S | T] = f[S] + 1;
                        pf[S | T] = make_tuple(T, i, j);
                    }
            }
    
    int cur = (1 << n) - 1;
    printf("%d\n", f[cur] - 1 + n);
    while (cur != 1) {
        auto [S, i, j] = pf[cur];
        print(S | (1 << i - 1) | (1 << j - 1), i, j);
        cur -= S;
    }
    return 0;
}